package pack;

public class TwoThreeFourTree
{
	public class Node
	{
		int type;
		int nodes;
		int num1;
		int num2;
		int num3;
		Node node1;
		Node node2;
		Node node3;
		Node node4;
		Node parent;

		public Node(int num)
		{
			this.type = 1;
			this.nodes = 0;
			this.num1 = num;
			this.parent = null;
		}
		
		public boolean insert(int num)
		{
			if(type == 1)
			{
				if(num < num1)
				{
					num2 = num1;
					num1 = num;
					node3 = node2;
					node2 = node1;
					node1 = null;
				}
				else if(num >= num1)
				{
					num2 = num;
//					node3 = null;
				}
				type++;
				if(nodes != 0)
					nodes++;
				return true;
			}
			else if(type == 2)
			{
				if(num < num1)
				{
					num3 = num2;
					num2 = num1;
					num1 = num;
					node4 = node3;
					node3 = node2;
					node2 = node1;
					node1 = null;
				}
				else if(num >= num1 && num < num2)
				{
					num3 = num2;
					num2 = num;
					node4 = node3;
					node3 = node2;
				}
				else if(num >= num2)
				{
					num3 = num;
//					node4 = null;
				}
				type++;
				if(nodes != 0)
					nodes++;
				return true;
			}
			return false;
		}
	}
	
	Node root;
	int lenght;

	public TwoThreeFourTree()
	{
		this.root = null;
		this.lenght = 0;
	}
	
	public TwoThreeFourTree(int mass[])
	{
		this.root = null;
		this.lenght = 0;
		for(int k = 0; k < mass.length; k++)
		{
			insert(mass[k]);
			System.out.println("\nInsert: " + mass[k]);
			printTree();
		}
	}
	
	public Node insert(int num)
	{
		lenght++;
		if(root == null)
		{
			root = new Node(num);
			return root;
		}
		
		return insert(num, root);
	}
	
	private Node insert(int num, Node node)
	{
		if(node.type == 3)
		{
			Node newNode = new Node(node.num2);
			newNode.node1 = new Node(node.num1);
			newNode.node2 = new Node(node.num3);
			
			newNode.nodes = 2;
			
			newNode.node1.node1 = node.node1;
			newNode.node1.node2 = node.node2;
			newNode.node2.node1 = node.node3;
			newNode.node2.node2 = node.node4;
			
			if(newNode.node1.node1 != null)
			{
				newNode.node1.nodes++;
				newNode.node1.node1.parent = newNode.node1;
			}
			if(newNode.node1.node2 != null)
			{
				newNode.node1.nodes++;
				newNode.node1.node2.parent = newNode.node1;
			}
			if(newNode.node2.node1 != null)
			{
				newNode.node2.nodes++;
				newNode.node2.node1.parent = newNode.node2;
			}
			if(newNode.node2.node2 != null)
			{
				newNode.node2.nodes++;
				newNode.node2.node2.parent = newNode.node2;
			}
			
			if(node == root)
			{
				newNode.node1.parent = newNode;
				newNode.node2.parent = newNode;
				root = newNode;
			}
			else
			{
				if(node.parent.insert(node.num2))
				{
					newNode.node1.parent = node.parent;
					newNode.node2.parent = node.parent;
					
					if(node.parent.type == 3 && node.parent.num3 == node.num2)
					{
						node.parent.node4 = newNode.node2;
						node.parent.node3 = newNode.node1;
					}
					else if(node.parent.type >= 2 && node.parent.num2 == node.num2)
					{
						node.parent.node3 = newNode.node2;
						node.parent.node2 = newNode.node1;
					}
					else if(node.parent.type >= 1 && node.parent.num1 == node.num2)
					{
						node.parent.node2 = newNode.node2;
						node.parent.node1 = newNode.node1;
					}
				}
				else
					System.out.println("1node.insert Bad!");				
			}
			
			if(num < newNode.num1)
				node = newNode.node1;
			else if(num >= newNode.num1)
				node = newNode.node2;
		}
		
		if(node.nodes == 0)
		{
			if(!node.insert(num))
				System.out.println("2node.insert Bad!");
			else
				return node;
		}
		else if(node.nodes == 2)
		{
			if(num < node.num1)
				node = insert(num, node.node1);
			else
				node = insert(num, node.node2);
		}
		else if(node.nodes == 3)
		{
			if(num < node.num1)
				node = insert(num, node.node1);
			else if(num >= node.num1 && num < node.num2)
				node = insert(num, node.node2);
			else if(num >= node.num3)
				node = insert(num, node.node3);
		}
		
		return node;
	}
	
	public void printTree()
	{
//		System.out.println("\nLenght: " + lenght);
//		System.out.println();
	
		if(root != null)
			printTree(root, 0, 1);
	}
	
	private void printTree(Node node, int level, int trail)
	{		
		if(node.node4 != null)
			printTree(node.node4, level+1, 4);
		
		if(node.node3 != null)
			printTree(node.node3, level+1, 3);
		
		if(node.type == 1)
			if(node.node2 != null)
				printTree(node.node2, level+1, 2);
		
		for(int k = 0; k < level; k++)
			System.out.print("\t");
		System.out.println(printNode(node));
		
		if(node.type != 1)
			if(node.node2 != null)
				printTree(node.node2, level+1, 2);
		
		if(node.node1 != null)
			printTree(node.node1, level+1, 1);
	}
	
	public String printNode(Node node)
	{
		if(node != null)
		{
			int trail = 0;
			if(node == root || node.parent.node1 == node)
				trail = 1;
			else if(node.parent.node2 == node)
				trail = 2;
			else if(node.parent.node3 == node)
				trail = 3;
			else if(node.parent.node4 == node)
				trail = 4;
			
			if(node.type == 1)
				return (String) (/*node.type + "|" + node.nodes + */trail + "[" + node.num1 + "]");
			else if(node.type == 2)
				return (String) (/*node.type + "|" + node.nodes + */trail + "[" + node.num1 + ", " + node.num2 + "]");
			else if(node.type == 3)
				return (String) (/*node.type + "|" + node.nodes + */trail + "[" + node.num1 + ", " + node.num2 + ", " + node.num3 + "]");
		}
		
		return null;
	}
	
	public Node search(int num)
	{
		Node parent = root;
		Node node = root;
		while(node != null)
		{
			int type = node.type;
			int num1 = node.num1;
			int num2 = node.num2;
			int num3 = node.num3;
			
			if((type == 3 && num3 == num) || (type >= 2 && num2 == num) || (type >= 1 && num1 == num))
				return node;
			else
			{
				parent = node;
				if(type == 3 && num > num3)
					node = node.node4;
				else if(type >= 2 && num > num2)
					node = node.node3;
				else if(type >= 1 && num > num1)
					node = node.node2;
				else
					node = node.node1;
			}
		}
		return parent;
	}
	
	public static void main(String[] args)
	{
//		int mass[] = {-9,-4,-5,5,4,4,2,5,6,0};
//		TwoThreeFourTree tree = new TwoThreeFourTree(mass);

		TwoThreeFourTree tree = new TwoThreeFourTree();
		int amount = 10;
		for(int k = 0; k < amount; k++)
		{
			int number = (int) (Math.random()*amount*2-amount);
			System.out.print(number + ",");
			tree.insert(number);
		}
		System.out.println();
		tree.printTree();
		
//		System.out.println("Remove: " + 4 + " : " + tree.remove(4));

		int search = (int) (Math.random()*amount*2-amount);
		Node searchNode = tree.search(search);
		System.out.println("Search: " + search);
		System.out.println("Node: " + tree.printNode(searchNode));
//		System.out.println("Remove: " + searchNum + " : " + tree.remove(searchNum));
//		System.out.println("Remove: " + searchNum/2 + " : " + tree.remove(searchNum/2));
//		System.out.println(tree.getMin());
//		System.out.println(tree.getMax());
//		
//		tree.printTree();
	}
}
